package mother_HeapSort;

/**
 * Created by xupeng20 on 2019/2/24.
 */
public class Java_Mother_HeapSort {
    /*
    给你一堆数，我可以加入数，告诉我我给你的数里面中最大数是什么，数组收集，复杂度比较高  堆结构单独用  并删除（大根堆之后最后一个和第一个交换删除）
     */
    public static int[] heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        //完成大根堆 二叉树的应用（数调整只用调整一条链，代价就是高度logn）
        //时间复杂度:log1 + log2 ..logn-  数学上收敛 ->O(n)
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        //完成排序  每次堆顶的拿出来放最后  在减少调整重排
        //时间复杂度:O(n.logn)   不稳定、常数项大  这才是堆排的真正复杂度
        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        while (heapSize>0){
            heapify(arr,1,heapSize);
            swap(arr,0,--heapSize);
        }
        return arr;
    }

    //大根堆
    public static void heapInsert(int[] arr, int index) {
        //index是数组中的下标 依次判断他在想像的数的什么位置
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }


    //排序
    public static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 - 1;
        while (left < heapSize && left> 0) {
            //选择孩子中较大数的下标
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //我孩子和我中选择出largest
            largest = arr[largest] > arr[index] ? largest : index;
            //没换跳出循环
            if (largest == index) {
                break;
            }
            //我孩子中有比我大，要往下换
            swap(arr, largest, index);
            //继续往下换
            index = largest;
            left = index * 2 + 1;
        }
    }

    //交换
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args){
        int [] arr = {1,3,2,4,5,6};
        int[] ints = heapSort(arr);
        for (int obj:ints){
            System.out.println(obj);
        }
    }
}
